package main.剑指OfferⅡ;

import java.util.*;

public class Day9_Day12 {
    public static void main(String[] args) {
        System.out.println("**************************Day09**************************");
        System.out.println("剑指OfferⅡ027.回文链表");
        System.out.println("剑指OfferⅡ028.展平多级双向链表");
        System.out.println("剑指OfferⅡ029.排序的循环链表");
        System.out.println("**************************Day10**************************");
        System.out.println("剑指OfferⅡ030.插入、删除和随机访问都是 O(1) 的容器");
        System.out.println("剑指OfferⅡ031.最近最少使用缓存");
        System.out.println("剑指OfferⅡ032.有效的变位词");
        System.out.println("**************************Day11**************************");
        System.out.println("剑指OfferⅡ033.变位词组");
        System.out.println("剑指OfferⅡ034.外星语言是否排序");
        System.out.println("剑指OfferⅡ035.最小时间差");
        System.out.println("**************************Day12**************************");
        System.out.println("剑指OfferⅡ036.后缀表达式");
        System.out.println("剑指OfferⅡ037.小行星碰撞");
        System.out.println("剑指OfferⅡ038.每日温度");
    }
}

//class Node {
//    public int val;
//    public Node prev;
//    public Node next;
//    public Node child;
//}
class Node {
    public int val;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _next) {
        val = _val;
        next = _next;
    }
};

class Offer27{
    public boolean isPalindrome(ListNode head) {
        List<Integer> list=new ArrayList<>();
        while (head!=null){
            list.add(head.val);
            head=head.next;
        }
        int size=list.size();
        for (int i=0;i<size/2;i++){
            if (list.get(i)!=list.get(size-1-i)) return false;
        }
        return true;
    }
}

class Offer28{
    public Node process(Node head){
        Node cur=head,last=null;
//        while (cur!=null){
//            Node next=cur.next;
//            if (cur.child!=null){
//                Node childLast=process(cur.child);
//                next=cur.next;
//                cur.next=cur.child;//连入子级链表
//                cur.child.prev=cur;
//                if (next!=null){//子级链表连入父级下一节点
//                    childLast.next=next;
//                    next.prev=childLast;
//                }
//                cur.child=null;
//                last=childLast;
//            }else {
//                last=cur;
//            }
//            cur=next;
//        }
        return last;
    }
    public Node flatten(Node head) {
        process(head);
        return head;
    }
}

class Offer29{
    public Node insert(Node head, int insertVal) {
        //节点为null的情况
        if (head == null) {
            Node node = new Node(insertVal);
            node.next = node;
            return node;
        }

        Node node = head;
        //开始循环,寻找链表的尾部 终止条件2选1:
        //1.当前节点大于下一个节点  2.下一个节点是头结点(证明所有节点值一样)
        while (node.val <= node.next.val && node.next != head) {
            node = node.next;
        }
        //找到了尾节点 判断insertVal是否大于等于尾节点或者小于等于头节点  是的话就在两节点中间插入
        if (insertVal >= node.val || insertVal <= node.next.val) {
            Node node1 = new Node(insertVal);
            node1.next = node.next;
            node.next = node1;
            return head;
        }
        //上一种情况不满足 那就继续循环节点 直到找到当node.val <= insertVal并且node.next.val>=insertVal
        while (node.val > insertVal || node.next.val < insertVal) {
            node = node.next;
        }
        Node node1 = new Node(insertVal);
        node1.next = node.next;
        node.next = node1;
        return head;
    }
}

class Offer30{
    private List<Integer> list;
    private int size;
    private Random random;
    public Offer30() {
        this.list=new ArrayList<>();
        this.size=0;
        this.random=new Random();
    }

    public boolean insert(int val) {
        if (list.contains(val)) return false;
        else {
            list.add(val);
            size++;
            return true;
        }
    }

    public boolean remove(int val) {
        Integer a=val;
        if (list.contains(val)) {
            list.remove(a);
            size--;
            return true;
        }else return false;
    }

    public int getRandom() {
        int index=0+random.nextInt(size);
        return list.get(index);
    }
}

class Offer31{
    public HashMap<Integer,Integer> hashMap=new HashMap<>();
    public Deque<Info> infos1=new ArrayDeque<>();
    public HashMap<Integer,Info> hashMap1=new HashMap<>();
    public int capacity;
    public static class Info{
        int key;
        int time;
        public Info(int key, int time) {
            this.key = key;
            this.time = time;
        }
    }
    public Offer31(int capacity) {
        this.capacity=capacity;
    }
    public int get(int key) {
        if (hashMap.containsKey(key)){
            Integer integer = hashMap.get(key);
            Info info = hashMap1.get(key);
            infos1.remove(info);
            info.time= Math.toIntExact(System.currentTimeMillis()>>11);
            infos1.addLast(info);
            return integer;
        }else {
            return -1;
        }
    }
    public void put(int key, int value) {
        if (hashMap.size()==capacity&&!hashMap.containsKey(key)){
            Info poll = infos1.pollFirst();
            hashMap.remove(poll.key);
            hashMap1.remove(poll.key);
            Info info = new Info(key, Math.toIntExact(System.currentTimeMillis()>>11));
            hashMap1.put(key,info);
            hashMap.put(key,value);
            infos1.addLast(info);
        }else {
            if (hashMap.containsKey(key)){
                hashMap.put(key,value);
                Info info = hashMap1.get(key);
                infos1.remove(info);
                info.time= (int) System.currentTimeMillis()>>11;
                infos1.addLast(info);
            }else {
                Info info = new Info(key, Math.toIntExact(System.currentTimeMillis()>>11));
                hashMap1.put(key,info);
                hashMap.put(key,value);
                infos1.addLast(info);
            }
        }
    }
}

class Offer32{
    public boolean isAnagram(String s, String t) {
        if (s.equals(t)) return false;
        int[] countS=new int[26],countT=new int[26];
        for (int i=0;i<s.length();i++){
            ++countS[s.charAt(i)-'a'];
        }
        for (int i=0;i<t.length();i++){
            ++countT[t.charAt(i)-'a'];
        }
        return Arrays.equals(countS,countT);
    }
}

class Offer33{
    public List<List<String>> groupAnagrams(String[] strs) {
        int length= strs.length;
        int[][] counts=new int[length][26];
        List<List<String>> list=new ArrayList<>();
        for (int i=0;i<length;i++){
            String temp=strs[i];
            for (int j=0;j<temp.length();j++){
                ++counts[i][temp.charAt(j)-'a'];
            }
        }
        boolean[] isUsed=new boolean[length];
        for (int i=0;i<length;i++){
            if (!isUsed[i]){
                List<String> curList=new ArrayList<>();
                curList.add(strs[i]);
                isUsed[i]=true;
                for (int j=i+1;j<length;j++){
                    if (Arrays.equals(counts[i],counts[j])){
                        isUsed[j]=true;
                        curList.add(strs[j]);
                    }
                }
                list.add(curList);
            }
        }
        return list;
    }
}

class Offer34{
    List<Character> orderList;
    public boolean isAlienSorted(String[] words, String order) {
        orderList=new ArrayList<>();
        for (char c:order.toCharArray()) orderList.add(c);
        String[] cloneWords=words.clone();
        Arrays.sort(cloneWords, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                char[] str1=o1.toCharArray(),str2=o2.toCharArray();
                int i=0,j=0;
                while (i<str1.length&&j< str2.length){
                    int index1=orderList.indexOf(str1[i]),index2= orderList.indexOf(str2[j]);
                    i++;
                    j++;
                    if (index1==index2) continue;
                    else if (index1<index2) return -1;
                    else return 1;
                }
                if (i==str1.length) return -1;
                else return 1;
            }
        });
        return Arrays.equals(words,cloneWords);
    }
}

class Offer35{
    public int process(String times){
        String[] time=times.split(":");
        int hour=Integer.valueOf(time[0]),minutes=Integer.valueOf(time[1]);
        int totalMinutes=hour*60+minutes;
        return totalMinutes;
    }
    public int findMinDifference(List<String> timePoints) {
        List<Integer> timeList=new ArrayList<>();
        for (String time:timePoints){
            timeList.add(process(time));
        }
        Collections.sort(timeList);
        timeList.add(timeList.get(0)+24*60);
        int result=24*60;
        for (int i=1;i<timeList.size();i++){
            result=Math.min(result,timeList.get(i)-timeList.get(i-1));
        }
        return result;
    }
}

class Offer36{
    public int evalRPN(String[] tokens) {
        Stack<String> stack=new Stack<>();
        int result=0,i=1,num1=0,num2=0;
        stack.add(tokens[0]);
        while (i< tokens.length){
            switch (tokens[i]){
                case "+":
                    num2=Integer.valueOf(stack.pop());
                    num1=Integer.valueOf(stack.pop());
                    num1=num1+num2;
                    stack.add(String.valueOf(num1));
                    break;
                case "-":
                    num2=Integer.valueOf(stack.pop());
                    num1=Integer.valueOf(stack.pop());
                    num1=num1-num2;
                    stack.add(String.valueOf(num1));
                    break;
                case "*":
                    num2=Integer.valueOf(stack.pop());
                    num1=Integer.valueOf(stack.pop());
                    num1=num1*num2;
                    stack.add(String.valueOf(num1));
                    break;
                case "/":
                    num2=Integer.valueOf(stack.pop());
                    num1=Integer.valueOf(stack.pop());
                    num1=num1/num2;
                    stack.add(String.valueOf(num1));
                    break;
                default:
                    stack.add(tokens[i]);
                    break;
            }
            i++;
        }
        result=Integer.valueOf(stack.pop());
        return result;
    }
}

class Offer37{
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> deque=new LinkedList<>();
        int i=asteroids.length-1;
        while (i>=0){
            if (deque.isEmpty()||deque.peekFirst()>0){//队首为空或为正数
                deque.addFirst(asteroids[i]);
            }else {//队首为负数
                int temp=deque.peekFirst();
                if (asteroids[i]<0){//新入队元素为负数
                    deque.addFirst(asteroids[i]);
                }else {//新入队元素为正数
                    if (temp+asteroids[i]==0){//大小相同
                        deque.pollFirst();
                    }else {//大小不同
                        while (temp<0&&temp+asteroids[i]>0){
                            deque.pollFirst();
                            if (!deque.isEmpty()) temp=deque.peekFirst();
                            else break;
                        }
                        if ((temp>0&&temp+asteroids[i]!=0)||deque.isEmpty()) deque.addFirst(asteroids[i]);
                        else if (temp+asteroids[i]==0) deque.pollFirst();
                    }
                }
            }
            i--;
        }
        int[] result=new int[deque.size()];
        for (int j=0;j< result.length;j++){
            result[j]=deque.pollFirst();
        }
        return result;
    }
}

class Offer38{
    public int[] dailyTemperatures(int[] temperatures) {
        int length= temperatures.length;
        int[] result=new int[length];
        Stack<Integer> stack=new Stack<>();
        for (int i=0;i<length;i++){
            while (!stack.isEmpty()&&temperatures[stack.peek()]<temperatures[i]){
                int index=stack.pop();
                result[index]=i-index;
            }
            stack.add(i);
        }
        return result;
    }
}